#include <iostream>
#include <vector>
#include <string>

// 构建部分匹配表（也称为"next"数组）
std::vector<int> computeLPSArray(const std::string& pattern) {
    int M = pattern.length();
    std::vector<int> lps(M, 0);

    int length = 0; // 前缀的长度
    int i = 1; // 索引，从1开始

    while (i < M) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// KMP算法实现
void KMPSearch(const std::string& pattern, const std::string& text) {
    int N = text.length();
    int M = pattern.length();

    std::vector<int> lps = computeLPSArray(pattern);

    int i = 0; // text的索引
    int j = 0; // pattern的索引

    while (i < N) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }

        if (j == M) {
            std::cout << "匹配在位置: " << i - j << std::endl;
            j = lps[j - 1];
        } else if (i < N && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i = i + 1;
            }
        }
    }
}

int main() {
    std::string text = "ABC ABCDAB ABCDABCDABDE";
    std::string pattern = "ABCDABD";
    KMPSearch(pattern, text);
    return 0;
}